// 2025/3/31
// https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked
// 乘积最大子数组

class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            long n = nums.size(), ans = nums[0];
            vector<long> dpMin(n + 1, 1), dpMax(n + 1, 1);
            for(int i = 1; i <= n; i++)
            {
                if(nums[i - 1] >= 0)
                {
                    dpMin[i] = min(dpMin[i - 1] * nums[i - 1], (long)nums[i - 1]);
                    dpMax[i] = max(dpMax[i - 1] * nums[i - 1], (long)nums[i - 1]);
                }
                else
                {
                    dpMin[i] = min(dpMax[i - 1] * nums[i - 1], (long)nums[i - 1]);
                    dpMax[i] = max(dpMin[i - 1] * nums[i - 1], (long)nums[i - 1]);
                }
                ans = max(ans, dpMax[i]);
            }
            return ans;
        }
    };